class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.val)


class Tree(object):
    def __init__(self):
        self.root = TreeNode("root")

    def add(self, val):
        node = TreeNode(val)
        if self.root is None:
            self.root = node  # 二叉树为空，直接插入根节点
        else:
            q = [self.root]
            while True:
                pop_node = q.pop(0)
                if pop_node.left is None:
                    pop_node.left = node
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)

    def get_parent(self, item):
        if self.root is None:
            return None  # 根节点没有父亲
